package main

import "fmt"

type (
	TreeArray [1024 * 1024]int
)

func (this *TreeArray) Lowbit(x int) int {
	return x & (-x)
}

func (this *TreeArray) Sum(i int) int {
	if i >= len(this) {
		return 0
	}

	s := 0
	for ; i > 0; i -= this.Lowbit(i) {
		s += this[i]
	}
	return s
}

func (this *TreeArray) Add(i, val int) {
	for ; i > 0 && i < len(this); i += this.Lowbit(i) {
		this[i] += val
	}
}

func (this *TreeArray) Build(arr []int) {
	for i, v := range arr {
		this[i] += v
		j := i + this.Lowbit(i)
		if j < len(this) {
			this[j] += this[i]
		}
	}
}

func (this *TreeArray) Rank(i int) int {
	return this.Sum(len(this)-1) - this.Sum(i) + 1
}

type (
	TopRank struct {
		table     string `sql:"table;name:tbl_toprank"`
		Id        int64  `sql:"primary;name:id" json:"id"`
		Type      int8   `sql:"primary;name:type" json:"type"`
		Name      string `sql:"name:name" json:"name"`
		Score     int    `sql:"name:score" json:"score"`
		Old_Score int    `sql:"name:score" json:"old_score"`
		Value     [2]int `sql:"name:value" json:"value"`
		LastTime  int64  `sql:"datetime;name:last_time" json:"last_time"`
	}
)

const (
	MAX_RANK_LEN = 10
)

type (
	TopMgr struct {
		m_topRankCachelMap map[int64]TopRank //排行榜队列
		m_topRankCacheSet  [MAX_RANK_LEN]TopRank
		m_topRankSet       [MAX_RANK_LEN]TopRank //排行榜队列
		m_topRankMap       map[int64]int
		m_treeArray        TreeArray
	}
)

//分布式考虑直接数据库
func (this *TopMgr) Init() {
	this.m_topRankCachelMap = map[int64]TopRank{}
	this.m_topRankMap = map[int64]int{}
}

func (this *TopMgr) insert(data TopRank) {
	this.m_topRankCachelMap[data.Id] = data
	this.m_treeArray.Add(data.Score, 1)
	this.m_treeArray.Add(data.Old_Score, -1)
}

func (this *TopMgr) do_sort() {
	for i := 0; i < MAX_RANK_LEN; i++ {
		this.m_topRankCacheSet[i] = this.m_topRankSet[i]
	}
	//清空榜上玩家
	for k, _ := range this.m_topRankCachelMap {
		rank, bEx := this.m_topRankMap[k]
		if bEx {
			this.m_topRankCacheSet[rank] = TopRank{}
		}
	}
	this.sort()
	for _, v := range this.m_topRankCachelMap {
		if this.m_topRankCacheSet[MAX_RANK_LEN-1].Score == 0 || v.Score > this.m_topRankCacheSet[MAX_RANK_LEN-1].Score {
			this.m_topRankCacheSet[MAX_RANK_LEN-1] = v
			this.sort()
		}
	}
	this.m_topRankCachelMap = map[int64]TopRank{}
	this.m_topRankMap = map[int64]int{}
	for i := 0; i < MAX_RANK_LEN; i++ {
		this.m_topRankSet[i] = this.m_topRankCacheSet[i]
		this.m_topRankMap[this.m_topRankSet[i].Id] = i
	}
}

func (this *TopMgr) sort() {
	//insert_sort
	for i := 1; i < MAX_RANK_LEN; i++ {
		temp := this.m_topRankCacheSet[i]
		j := i - 1
		for ; j >= 0 && this.m_topRankCacheSet[j].Score < temp.Score; j-- {
			this.m_topRankCacheSet[j+1] = this.m_topRankCacheSet[j]
		}
		this.m_topRankCacheSet[j+1] = temp
	}
}

func (this *TopMgr) show() {
	fmt.Println(this.m_topRankCacheSet, this.m_treeArray.Rank(100))
}

func main() {
	t := TopMgr{}
	t.Init()
	for i := 0; i < 103; i++ {
		dat := TopRank{Id: int64(i), Score: i + 1}
		t.insert(dat)
	}
	t.do_sort()
	t.show()
	for i := 0; i < 103; i++ {
		dat := TopRank{Id: int64(i), Score: 104 - i, Old_Score: i + 1}
		t.insert(dat)
	}
	t.do_sort()
	t.show()
	for i := 0; i < 103; i++ {
		dat := TopRank{Id: int64(i), Score: i + 1, Old_Score: 104 - i}
		t.insert(dat)
	}
	t.do_sort()
	t.show()
}
